A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization

摘要

The block coordinate descent (BCD) method is widely used for minimizing acontinuous function f of several block variables. At each iteration of thismethod, a single block of variables is optimized, while the remaining variablesare held fixed. To ensure the convergence of the BCD method, the subproblem tobe optimized in each iteration needs to be solved exactly to its unique optimalsolution. Unfortunately, these requirements are often too restrictive for manypractical scenarios. In this paper, we study an alternative inexact BCDapproach which updates the variable blocks by successively minimizing asequence of approximations of f which are either locally tight upper bounds off or strictly convex local approximations of f. We focus on characterizing theconvergence properties for a fairly wide class of such methods, especially forthe cases where the objective functions are either non-differentiable ornonconvex. Our results unify and extend the existing convergence results formany classical algorithms such as the BCD method, the difference of convexfunctions (DC) method, the expectation maximization (EM) algorithm, as well asthe alternating proximal minimization algorithm.